package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DivideConquer;
import cn.pugle.oj.catalog.DynamicProblem;

/**
 * 144 ms, faster than 22.78%
 * <p>
 * todo 分治, 找中轴 好像更快
 * https://www.cnblogs.com/en-heng/p/3973679.html
 * https://leetcode.com/problems/longest-palindromic-substring/discuss/762594/99-Fast-Java-Very-easy-Solution
 * <p>
 * 哦哦, 原来是这道题我在字符串上面使用了一种基于步长的遍历方式,
 * 先步长1, 判断所有start+step是不是回文
 * 然后步长2, 步长3, 直到最大.
 *
 * @author tzp
 * @since 2020/9/12
 */
public class LC5_1 implements DynamicProblem, DivideConquer {
    public String longestPalindrome(String s) {
        boolean[][] state = new boolean[s.length()][s.length()];
        String max = "";
        for (int step = 1; step <= s.length(); step++) {
            for (int start = 0; start < s.length(); start++) {
                if (start + step > s.length()) {
                    break;
                }
                if (step == 1) {
                    state[start][start + step - 1] = true;
                } else if ((s.charAt(start) == s.charAt(start + step - 1))) {
                    if (step == 2) {
                        state[start][start + step - 1] = true;
                    } else {
                        state[start][start + step - 1] = state[start + 1][start + step - 2];
                    }
                } else {
                    state[start][start + step - 1] = false;
                }

                if (state[start][start + step - 1] && step > max.length()) {
                    max = s.substring(start, start + step);
                }
            }
        }
        return max;
    }


    public static void main(String[] args) {
        System.out.println(new LC5_1().longestPalindrome(""));
        System.out.println(new LC5_1().longestPalindrome("a"));
        System.out.println(new LC5_1().longestPalindrome("aba"));
        System.out.println(new LC5_1().longestPalindrome("bbbab"));
        System.out.println(new LC5().longestPalindrome("civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"));
    }
}
